package com.zk.algorithm;

import com.zk.algorithm.bean.Element;
import com.zk.algorithm.bean.ListNode;
import com.zk.algorithm.factory.ListFactory;
import javafx.collections.transformation.SortedList;

/**
 * https://leetcode.com/problems/sort-list/description/
 *
 * Sort a linked list in O(n log n) time using constant space complexity.
 */
public class SortList {

    public static void main(String...args) {
        Utils.println(new SortList().sortList(ListFactory.create(new int[]{-1,5,3,4,0,6})));
    }

    public ListNode sortList(ListNode head) {
        return sortByMergeSort(head);
    }

    // ==============================
    // 链表归并排序
    // https://leetcode.com/problems/sort-list/discuss/46714/Java-merge-sort-solution
    // ==============================
    private ListNode sortByMergeSort(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode[] splited = split(head);
        ListNode halfOne = sortList(splited[0]);
        ListNode halfTwo = sortList(splited[1]);

        return merge(halfOne, halfTwo);
    }

    private ListNode[] split(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        // -1,5,3,4,0,6
        //          f
        //      s
        //
        // -1,5,3,4,0
        //          f
        //      s
        //
        // -1,5
        // f
        // s
        //
        while (fast != null &&
                fast.next != null &&
                fast.next.next != null) {

            fast = fast.next.next;
            slow = slow.next;

        }

        ListNode halfTwo = slow.next;
        ListNode halfOne = head;

        slow.next = null;
        return new ListNode[]{ halfOne, halfTwo };
    }

    private ListNode merge(ListNode a, ListNode b) {
        ListNode headA = a;
        ListNode headB = b;

        ListNode headC = new ListNode(-1);
        ListNode headCPointer = headC;

        while (headA != null && headB != null) {

            if (headA.val > headB.val) {
                headCPointer.next = headB;
                // 指针走错了
                headB = headB.next;
            } else {
                headCPointer.next = headA;
                headA = headA.next;
            }

            headCPointer = headCPointer.next;
        }

        // 优化
        // headCPointer.next = headA
        while (headA != null) {
            headCPointer.next = headA;

            headA = headA.next;
            headCPointer = headCPointer.next;
        }

        // 优化
        // headCPointer.next = headB
        while (headB != null) {
            headCPointer.next = headB;

            headB = headB.next;
            headCPointer = headCPointer.next;
        }

        return headC.next;
    }

    // ==============================
    // 链表快速排序
    // https://leetcode.com/problems/sort-list/discuss/46714/Java-merge-sort-solution
    // ==============================

}
